singlepass聚类算法实现天气聚类

系统聚类法的基本思想是&＃xff1a;距离近的样品先聚成类&＃xff0c;距离远的后聚成类。

根据类间定义的不同&＃xff0c;系统聚类法又可以分成最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法、离差平方和法8种。

需要注意的是&＃xff1a;

&＃xff08;1&＃xff09;该方法不需要事先指定聚类个数&＃xff0c;而是根据最终的分类过程确定。

&＃xff08;2&＃xff09;为了直观的反映&＃xff0c;可以把分类系统画成一张谱系图&＃xff0c;所以系统聚类也称谱系分析。

K-means聚类法是非常经典的聚类算法&＃xff0c;有关资料很丰富&＃xff0c;故本文不再赘述。

需要注意的是&＃xff1a;

&＃xff08;1&＃xff09;该方法通过计算欧氏距离&＃xff0c;比较样品间的相似度进行聚类。不过我也有看过&＃xff0c;通过计算相关系数来聚类的。

&＃xff08;2&＃xff09;该法需要指定聚类个数&＃xff0c;而K的确定是个难点&＃xff0c;有很多针对K优化的方法。

Single-pass clustering&＃xff0c;中文名一般译作“单遍聚类”&＃xff0c;它是一种简洁且高效的文本聚类算法。相比于常用的K-means聚类法&＃xff0c;它的计算速度非常快&＃xff0c;且不需要指定聚类个数&＃xff0c;而是通过设定相似度阈值来限定。

Single-pass聚类算法同时是一种增量聚类算法&＃xff08;Incremental Clustering Algorithm&＃xff09;&＃xff0c;每个文档只需要流过算法一次&＃xff0c;常用与文本主题的聚类中。它可以很好的应用于话题监测与追踪、在线事件监测等社交媒体大数据领域&＃xff0c;特别适合流式数据&＃xff08;Streaming Data&＃xff09;&＃xff0c;比如微博的帖子信息等。

流数据:一组顺序、大量、快速、连续到达的数据序列。一般情况下&＃xff0c;流数据可被视为一个随时间延续而无限增长的动态数据集合。 来源&＃xff1a;百度百科

Single-pass算法顺序处理文本&＃xff0c;以第一篇文档为种子&＃xff0c;建立一个新主题。之后再进行新进入文档与已有主题的相似度&＃xff0c;将该文档加入到与它相似度最大的、且大于一定阈值的主题中。如果与所有已有话题相似度都小于阈值&＃xff0c;则以该文档为聚类种子&＃xff0c;建立新的主题类别。其算法流程如下&＃xff1a;

&＃xff08;1&＃xff09;以第一篇文档为种子&＃xff0c;建立一个主题&＃xff1b;

&＃xff08;2&＃xff09;将文档X向量化&＃xff1b;

&＃xff08;3&＃xff09;将文档X与已有的所有话题均做相似度计算&＃xff0c;可采用欧氏距离或余弦距离等距离度量方法

&＃xff08;4&＃xff09;找出与文档X具有最大相似度的已有主题&＃xff1b;

&＃xff08;5&＃xff09;若相似度值大于阈值θ &＃xff0c;则把文档X加入到有最大相似度的主题中&＃xff0c;跳转至 &＃xff08;7&＃xff09;&＃xff1b;

&＃xff08;6&＃xff09;若相似度值小于阈值θ &＃xff0c; 则文档X不属于任一已有主题&＃xff0c; 需创建新的主题类别&＃xff0c;同时将当前文本归属到新创建的主题类别中&＃xff1b;

&＃xff08;7&＃xff09;聚类结束&＃xff0c;等待下一篇文档进入

注&＃xff1a;上述中讲相似度最大的划为一类&＃xff0c;在实际代码中&＃xff0c;所谓相似度最大大于某个阈值&＃xff0c;也可以理解为距离最近&＃xff08;小&＃xff09;小于某个阈值。

将样本信息保存至TXT文件中&＃xff0c;截图后如上所示。

有多少行我没数&＃xff0c;用python中describe()一下就知道了&＃xff0c;列数是十列。

日期后面两类是最高温和最低温&＃xff0c;最后两列表示该地的经度和纬度。

首先定义了一个簇单元 ClusterUnit &＃xff0c;定义了一个单类 OnePassCluster &＃xff0c;定义了向量a与b间的欧式距离euclidian_distance。

# coding&＃61;utf-8import numpy as npfrom math import sqrtimport timeimport matplotlib.pylab as pl# 定义一个簇单元class ClusterUnit:def __init__(self):self.node_list &＃61; [] # 该簇存在的节点列表self.node_num &＃61; 0 # 该簇节点数self.centroid &＃61; None # 该簇质心def add_node(self, node, node_vec):"""为本簇添加指定节点&＃xff0c;并更新簇心node_vec:该节点的特征向量node:节点return:null"""self.node_list.append(node)try:self.centroid &＃61; (self.node_num * self.centroid &＃43; node_vec) / (self.node_num &＃43; 1) # 更新簇心except TypeError:self.centroid &＃61; np.array(node_vec) * 1 # 初始化质心self.node_num &＃43;&＃61; 1 # 节点数加1def remove_node(self, node):# 移除本簇指定节点try:self.node_list.remove(node)self.node_num -&＃61; 1except ValueError:raise ValueError("%s not in this cluster" % node) # 该簇本身就不存在该节点&＃xff0c;移除失败def move_node(self, node, another_cluster):# 将本簇中的其中一个节点移至另一个簇self.remove_node(node&＃61;node)another_cluster.add_node(node&＃61;node)# cluster_unit &＃61; ClusterUnit()# cluster_unit.add_node(1, [1, 1, 2])# cluster_unit.add_node(5, [2, 1, 2])# cluster_unit.add_node(3, [3, 1, 2])# print(cluster_unit.centroid)# 计算向量a与向量b的欧式距离def euclidian_distance(vec_a, vec_b):diff &＃61; vec_a - vec_breturn sqrt(np.dot(diff, diff)) # dot计算矩阵内积class OnePassCluster:def __init__(self, t, vector_list):# t:一趟聚类的阈值self.threshold &＃61; t # 一趟聚类的阈值self.vectors &＃61; np.array(vector_list) # 数据列表&＃xff08;向量列表&＃xff09;self.cluster_list &＃61; [] # 聚类后簇的列表t1 &＃61; time.time()self.clustering()t2 &＃61; time.time()self.cluster_num &＃61; len(self.cluster_list) # 聚类完成后 簇的个数self.spend_time &＃61; t2 - t1 # 聚类花费的时间def clustering(self):self.cluster_list.append(ClusterUnit()) # 初始新建一个簇self.cluster_list[0].add_node(0, self.vectors[0]) # 将读入的第一个节点归于该簇for index in range(len(self.vectors))[1:]:min_distance &＃61; euclidian_distance(vec_a&＃61;self.vectors[index],vec_b&＃61;self.cluster_list[0].centroid) # 与簇的质心的最小距离min_cluster_index &＃61; 0 # 最小距离的簇的索引for cluster_index, cluster in enumerate(self.cluster_list[1:]):# enumerate会将数组或列表组成一个索引序列# 寻找距离最小的簇&＃xff0c;记录下距离和对应的簇的索引distance &＃61; euclidian_distance(vec_a&＃61;self.vectors[index],vec_b&＃61;cluster.centroid)if distance min_distance:min_distance &＃61; distancemin_cluster_index &＃61; cluster_index &＃43; 1if min_distance self.threshold: # 最小距离小于阈值&＃xff0c;则归于该簇self.cluster_list[min_cluster_index].add_node(index, self.vectors[index])else: # 否则新建一个簇new_cluster &＃61; ClusterUnit()new_cluster.add_node(index, self.vectors[index])self.cluster_list.append(new_cluster)del new_clusterdef print_result(self, label_dict&＃61;None):# 打印出聚类结果# label_dict:节点对应的标签字典print("*********** single-pass的聚类结果展示 ***********")for index, cluster in enumerate(self.cluster_list):print("cluster:%s" % index) # 簇的序号print(cluster.node_list) # 该簇的节点列表if label_dict is not None:print(" ".join([label_dict[n] for n in cluster.node_list])) # 若有提供标签字典&＃xff0c;则输出该簇的标签print("node num: %s" % cluster.node_num)print( "-------------")print( "所有节点的个数为&＃xff1a; %s" % len(self.vectors))print("簇类的个数为&＃xff1a;%s" % self.cluster_num)print("花费的时间为&＃xff1a; %.9fs" % (self.spend_time / 1000))

运行之后&＃xff0c;一共聚类十类&＃xff0c;聚类个数从0-9。

如下图为第八个类别所包含的城市以及他们对应的索引&＃xff1a; 整体运行结果如下&＃xff1a;

之后通过实例化类和调用函数&＃xff0c;来实现聚类

# 读取测试集temperature_all_city &＃61; np.loadtxt(&＃39;data1.txt&＃39;, delimiter&＃61;",", usecols&＃61;(3, 4),encoding&＃61;&＃39;utf-8&＃39;) # 读取聚类特征xy &＃61; np.loadtxt(&＃39;data1.txt&＃39;, delimiter&＃61;",", usecols&＃61;(8, 9),encoding&＃61;&＃39;utf-8&＃39;) # 读取各地经纬度f &＃61; open(&＃39;data1.txt&＃39;, &＃39;r&＃39;,encoding&＃61;&＃39;utf-8&＃39;)lines &＃61; f.readlines()zone_dict &＃61; [i.split(&＃39;,&＃39;)[1] for i in lines] # 读取地区并转化为字典f.close()# 构建一趟聚类器clustering &＃61; OnePassCluster(vector_list&＃61;temperature_all_city, t&＃61;9)clustering.print_result(label_dict&＃61;zone_dict)print(temperature_all_city)# 将聚类结果导出图fig, ax &＃61; pl.subplots()fig &＃61; zone_dictc_map &＃61; pl.get_cmap(&＃39;jet&＃39;, clustering.cluster_num)c &＃61; 0for cluster in clustering.cluster_list:for node in cluster.node_list:#ax.scatter(xy[node][0], xy[node][1], c&＃61;c, s&＃61;30, cmap&＃61;c_map, vmin&＃61;0, vmax&＃61;clustering.cluster_num)ax.scatter(xy[node][0], xy[node][1])c &＃43;&＃61; 1#pl.axis(&＃39;off&＃39;) # 不显示坐标轴pl.savefig(&＃39;./map.jpg&＃39;)pl.show()

根据样本中经纬度的信息&＃xff0c;并结合聚类算法的结果&＃xff0c;可画图如下&＃xff1a;

本文主要给出single-pass聚类算法的实例&＃xff0c;该例很好复现。希望对各位兄弟姐妹们有所帮助。

参考&＃xff1a;https://blog.csdn.net/maqian5/article/details/107333316

本文数据与代码均引用他处&＃xff0c;如未标注来源&＃xff0c;请联系我更改加上。

需要本文数据和代码&＃xff0c;可在本文评论区留言。希望对各位兄弟姐妹们有所帮助。